Chihik's Blog

An Ac a day, keeps the doctor away!

区间dp

置顶 | 发布于 2020-07-11 | 分类于 dp 、 区间dp | 19分钟 | 3285字数

一.概念

对于一段区间求最优解，且该区间可以分为几个小区间的最优解合并（最优子结构）。

二.基本思路

阅读全文 »

伯努利数

置顶 | 发布于 2020-07-11 | 分类于 数学 、 伯努利数 | 8分钟 | 1346字数

伯努利数是一个用于解决 nn 次方和的数列。

它的递归定义公式如下：

∑i=0n(n+1i)Bi=[n=0]        (1.1)\sum_{i=0}^n \binom {n+1}{i} B_i=[n=0] ~~~~~~~~ (1.1)

阅读全文 »

LOJ528 求和

发布于 2021-03-01 | 分类于 莫比乌斯反演 | 4分钟 | 569字数

∑i=1n∑j=1mμ2(gcd⁡(i,j))\sum_{i=1}^n\sum_{j=1}^m \mu^2(\gcd(i,j))

∑d=1min⁡(n,m)μ2(d)∑i=1n∑j=1m[gcd⁡(i,j)=d]\sum_{d=1}^{\min(n,m)}\mu^2(d)\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=d]

阅读全文 »

P3703 [SDOI2017]树点涂色

发布于 2021-02-25 | 分类于 动态树 | 6分钟 | 972字数

众所周知，access(x)\text{access(x)} 后 rt→xrt \to x 这条实链在一个 splaysplay 中。也就是说， splaysplay 所维护的链中的点同色。

那么到点 xx 到根路径的权值便是经过虚边的数量 +1+1，不妨记为 disxdis_x。

0%